#pragma once
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<stdlib.h>
#include<assert.h>
#include<time.h>
using namespace std;

namespace A {
	template<class T> 
	struct list_node {
		struct list_node<T>* _pre=nullptr;
		struct list_node<T>* _next=nullptr;
		T _data;

		list_node(const T& data=T()) {
			_data = data;
		}
	};

	template<class T,class Ref,class Ptr>
	class list_iterator {
	public:
		typedef list_node<T> node;
		typedef list_iterator<T, Ref,Ptr> self;
		node* _node=nullptr;

	public:
		list_iterator( node* x) {
			_node =x;
		}

		self& operator++() {
			_node = _node->_next;
			return *this;
		}

		self operator++(int) {
			self tmp(*this);
			++*this;
			//_node = _node->_next;
			return tmp;
		}

		self& operator--() {
			_node = _node->_pre;
			return *this;
		}

		self operator--(int) {
			self tmp(*this);
			--*this;
			return tmp;
		}

		Ref operator*()const {
			return _node->_data;
		}

		Ptr operator->()const {
			return &_node->_data;
		   }

		bool operator!=(const self cmp_node)const {
			return _node!=cmp_node._node;
		}

		bool operator==(const self it) {
			return _node == it._node;
		}
	};

	template<class Iterator, class Ref, class Ptr>
	struct ReverseIterator {
		typedef ReverseIterator<Iterator, Ref, Ptr> Self;

		Iterator _it;

		ReverseIterator(Iterator it)
			:_it(it)
		{}

		Ref operator*()const  {
			Iterator tmp = _it;
			return *--tmp;
		}

		Ptr operator->()const {
			return &(operator*());
		}

		Self& operator++() {
			--_it;
			return *this;
		}

		Self& operator--() {
			++_it;
			return *this;
		}

		Self rbegin() {
			return Self(_it.end());

		}

		Self rend() {
			return Self(_it.begin());
		}

		bool operator!=(const Self& x) {
			return _it != x._it;
		}
	};


	template<class T>
	class list {
		typedef list_node<T> node;
	public:
		typedef list_iterator<T,T&,T*> iterator;
		typedef  list_iterator<T, const T&,const T*> const_iterator;
		typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
		typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
	private: 
		node* _head;

	public:
		list() {
			_head = new node;
			_head->_pre = _head;
			_head->_next = _head;
		}

		list(const list<T>& lt) {
			_head = new node;
			_head->_pre = _head;
			_head->_next = _head;
			for (T& e : lt) {
				push_back(e);
			}
		}

		void swap(list<T>& lt) {
			std::swap(_head, lt._head);
		}

		list<T>& operator=(list<T> lt) {
			swap(lt);
			return *this;
		}

		void clear() {
			iterator it = begin();
			while (it != end())
				it = erase(it);
		}

		~list() {
			iterator it = begin();
			while (it != end()) {
				it = erase(it);
			}
			delete _head;
			_head = nullptr;
		}

		void push_back(const T& val) {
			node* newnode = new node(val);
			//list_node<T>* tail = _head->_pre;
			_head->_pre->_next = newnode;
			newnode->_pre = _head->_pre;
			newnode->_next = _head;
			_head->_pre = newnode;
		}

		void push_front(const T& val) {
			node* newnode = new node(val);
			node* front = _head->_next;
			_head->_next = newnode;
			newnode->_pre = _head;
			newnode->_next = front;
			front ->_pre = newnode->_next;
		}

		void pop_front() {
			erase(begin());
		}

		void pop_back() {
			erase(--end());
		}

		iterator begin() {
			return _head->_next;
		}

		 iterator end() {
			return _head;
		}

		const_iterator begin()const {
			 return _head->_next;
		}

		const_iterator end()const {
			 return _head;
		 }

		iterator erase(iterator position) {
			assert(position != end());
			node* cur = position._node;
			cur->_pre->_next = cur->_next;
			cur->_next->_pre = cur->_pre;
			node* ret = cur->_next;
			delete cur;
			return ret;
		}

		size_t  size() {
			size_t sz = 0;
			for (auto& e : *this) {
				++sz;
			}
			return sz;
		}

		bool empty() {
			return size() == 0;
		}

		iterator insert(iterator position, const T& val) {
			node* newnode = new node(val);
			node* next = position._node;
			node* pre = position._node->_pre;
			pre->_next = newnode;
			newnode->_pre = pre;

			next->_pre = newnode;
			newnode->_next = next;
			return newnode;
		}
	};


}
